{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# q2-q3\n",
    "hidden = []\n",
    "\n",
    "def subset_sum(numbers, target, partial=[]):\n",
    "    s = sum(partial)\n",
    "\n",
    "    # check if the partial sum is equals to target\n",
    "    if s == target:\n",
    "        # print(\"sum(%s)=%s\" % (partial, target))\n",
    "        hidden.append(partial)\n",
    "    if s >= target:\n",
    "        return  # if we reach the number why bother to continue\n",
    "\n",
    "    for i in range(len(numbers)):\n",
    "        n = numbers[i]\n",
    "        remaining = numbers[i:]\n",
    "        subset_sum(remaining, target, partial + [n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "最多情况:  522 \n",
      "最少情况:  46\n"
     ]
    }
   ],
   "source": [
    "subset_sum([i+1 for i in range(36)], 36)\n",
    "maxi = 0; mini = 1000\n",
    "for i in range(len(hidden)):\n",
    "    wnum = 0\n",
    "    hidden[i].append(1)\n",
    "    for j in range(len(hidden[i])-1):\n",
    "        wnum += hidden[i][j]*hidden[i][j+1]\n",
    "    wnum += 10*hidden[i][0]\n",
    "    maxi = wnum if wnum>maxi else maxi\n",
    "    mini = wnum if wnum<mini else mini\n",
    "print('最多情况: ', maxi, '\\n最少情况: ', mini)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# 初始化theta函数\n",
    "def inittheta(d, M, r):\n",
    "    theta1 = np.random.uniform(-r, r, (d, M))\n",
    "    theta2 = np.random.uniform(-r, r, (M+1, 1))\n",
    "    return theta1, theta2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# tanh的导数函数\n",
    "def dertanh(s):\n",
    "    return 1-np.tanh(s)**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# 神经网络函数---BP更新参数\n",
    "def nnetwork(X, Y, M, r, eta, T):\n",
    "    row, col = X.shape\n",
    "    theta1, theta2 = inittheta(col, M, r)\n",
    "    for i in range(T):\n",
    "        # 前向传播\n",
    "        randpos = np.random.randint(0, row)\n",
    "        xone = X[randpos: randpos+1, :]\n",
    "        yone = Y[randpos]\n",
    "        s1 = xone.dot(theta1)\n",
    "        x1 = np.tanh(s1)\n",
    "        x1 = np.c_[np.ones((1, 1)), x1]\n",
    "        s2 = x1.dot(theta2)\n",
    "        x2 = np.tanh(s2)[0][0]\n",
    "        delta2 = -2*(yone-x2)\n",
    "        delta1 = delta2*theta2[1:, :].T*dertanh(s1)\n",
    "        theta2 -= eta*x1.T*delta2\n",
    "        theta1 -= eta*xone.T.dot(delta1)\n",
    "    return theta1, theta2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# 误差衡量函数\n",
    "def errfun(X, Y, theta):\n",
    "    row, col = X.shape\n",
    "    l = len(theta)\n",
    "    x = X\n",
    "    for i in range(l-1):\n",
    "        x = np.c_[np.ones((row, 1)), np.tanh(x.dot(theta[i]))]\n",
    "    x2 = np.tanh(x.dot(theta[l-1]))\n",
    "    Yhat = x2\n",
    "    Yhat[Yhat>=0] = 1\n",
    "    Yhat[Yhat<0] = -1\n",
    "    return np.sum(Yhat != Y)/row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# 加载数据函数\n",
    "def loadData(filename):\n",
    "    data = pd.read_csv(filename, sep='\\s+', header=None)\n",
    "    data = data.as_matrix()\n",
    "    col, row = data.shape\n",
    "    X = np.c_[np.ones((col, 1)), data[:, 0: row-1]]\n",
    "    Y = data[:, row-1: row]\n",
    "    return X, Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "X, Y = loadData('hw4_nnet_train.dat')\n",
    "Xtest, Ytest = loadData('hw4_nnet_test.dat')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0.30592   0.036192  0.03624   0.036248  0.036408]\n"
     ]
    }
   ],
   "source": [
    "# Q11\n",
    "M = [1, 6, 11, 16, 21]\n",
    "eout = np.zeros((len(M),))\n",
    "for i in range(500):\n",
    "    for j in range(len(M)):\n",
    "        theta1, theta2 = nnetwork(X, Y, M[j], 0.1, 0.1, 50000)\n",
    "        theta = [theta1, theta2]\n",
    "        eout[j] += errfun(Xtest, Ytest, theta)\n",
    "print(eout/500)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0.49328  0.036    0.16184  0.3832   0.40072]\n"
     ]
    }
   ],
   "source": [
    "# Q12\n",
    "r = [0, 0.1, 10, 100, 1000]\n",
    "eout = np.zeros((len(r),))\n",
    "for i in range(50):\n",
    "    for j in range(len(r)):\n",
    "        theta1, theta2 = nnetwork(X, Y, 3, r[j], 0.1, 50000)\n",
    "        theta = [theta1, theta2]\n",
    "        eout[j] += errfun(Xtest, Ytest, theta)\n",
    "print(eout / 50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false,
    "deletable": true,
    "editable": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0.0808  0.036   0.036   0.4832  0.52  ]\n"
     ]
    }
   ],
   "source": [
    "# Q13\n",
    "eta = [0.001, 0.01, 0.1, 1, 10]\n",
    "eout = np.zeros((len(eta),))\n",
    "for i in range(5):\n",
    "    for j in range(len(eta)):\n",
    "        theta1, theta2 = nnetwork(X, Y, 3, 0.1, eta[j], 50000)\n",
    "        theta = [theta1, theta2]\n",
    "        eout[j] += errfun(Xtest, Ytest, theta)\n",
    "print(eout / 5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true,
    "deletable": true,
    "editable": true
   },
   "outputs": [],
   "source": [
    "# 多层神经网络\n",
    "def nnetwork2hidden(X, Y, d1, d2, T):\n",
    "    row, col = X.shape\n",
    "    theta1 = np.random.uniform(-0.1, 0.1, (col, d1))\n",
    "    theta2 = np.random.uniform(-0.1, 0.1, (d1+1, d2))\n",
    "    theta3 = np.random.uniform(-0.1, 0.1, (d2+1, 1))\n",
    "    for i in range(T):\n",
    "        # 前向传播\n",
    "        randpos = np.random.randint(0, row)\n",
    "        xone = X[randpos: randpos+1, :]\n",
    "        yone = Y[randpos]\n",
    "        s1 = xone.dot(theta1)\n",
    "        x1 = np.tanh(s1)\n",
    "        x1 = np.c_[np.ones((1, 1)), x1]\n",
    "        s2 = x1.dot(theta2)\n",
    "        x2 = np.tanh(s2)\n",
    "        x2 = np.c_[np.ones((1, 1)), x2]\n",
    "        s3 = x2.dot(theta3)\n",
    "        x3 = np.tanh(s3)[0][0]\n",
    "        delta3 = -2*(yone-x3)\n",
    "        delta2 = delta3*theta3[1:, :].T*dertanh(s2)\n",
    "        delta1 = delta2.dot(theta2[1:, :].T)*dertanh(s1)\n",
    "        theta3 -= 0.01*x2.T*delta3\n",
    "        theta2 -= 0.01*x1.T*delta2\n",
    "        theta1 -= 0.01*xone.T.dot(delta1)\n",
    "    return theta1, theta2, theta3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.036\n"
     ]
    }
   ],
   "source": [
    "# Q14\n",
    "eout = 0\n",
    "for i in range(50):\n",
    "    theta1, theta2, theta3 = nnetwork2hidden(X, Y, 8, 3, 50000)\n",
    "    theta = [theta1, theta2, theta3]\n",
    "    eout += errfun(Xtest, Ytest, theta)\n",
    "print(eout/50)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#---------kNN----------------\n",
    "def kNNeighbor(k, xpred, X, Y):\n",
    "    xmin = np.sum((xpred - X)**2, 1)\n",
    "    pos = np.argsort(xmin, 0)\n",
    "    Ypred = Y[pos[0:k]]\n",
    "    Ypred = np.sum(Ypred)\n",
    "    Ypred = 1 if Ypred>=0 else -1\n",
    "    return Ypred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 预测函数\n",
    "def predict(Xtest, X, Y, k):\n",
    "    row, col = Xtest.shape\n",
    "    Ypred = np.zeros((row, 1))\n",
    "    for i in range(row):\n",
    "        Ypred[i] = kNNeighbor(k, Xtest[i, :], X, Y)\n",
    "    return Ypred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 加载数据函数\n",
    "def loadData(filename):\n",
    "    data = pd.read_csv(filename, sep='\\s+', header=None)\n",
    "    data = data.as_matrix()\n",
    "    col, row = data.shape\n",
    "    X = data[:, 0: row-1]\n",
    "    Y = data[:, row-1:row]\n",
    "    return X, Y"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 导入数据\n",
    "X, Y = loadData('hw4_knn_train.dat')\n",
    "Xtest, Ytest = loadData('hw4_knn_test.dat')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.344\n"
     ]
    }
   ],
   "source": [
    "# Q15-Q16\n",
    "Yhat = predict(Xtest, X, Y, 1)\n",
    "eout = np.sum(Yhat!=Ytest)/Ytest.shape[0]\n",
    "print(eout)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.16 0.316\n"
     ]
    }
   ],
   "source": [
    "# Q17-Q18\n",
    "Yhat1 = predict(X, X, Y, 5)\n",
    "Yhat2 = predict(Xtest, X, Y, 5)\n",
    "ein = np.sum(Yhat1 != Y) / Y.shape[0]\n",
    "eout = np.sum(Yhat2 != Ytest) / Ytest.shape[0]\n",
    "print(ein, eout)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# -----------kMeans------------\n",
    "def kMean(k, X):\n",
    "    row, col = X.shape\n",
    "    pos = np.random.permutation(row)\n",
    "    mu = X[pos[0: k], :]\n",
    "    epsilon = 1e-5; simi = 1\n",
    "    while simi>epsilon:\n",
    "        S = np.zeros((row, k))\n",
    "        for i in range(k):\n",
    "            S[:, i] = np.sum((X-mu[i, :])**2, 1)\n",
    "        tempmu = mu.copy()\n",
    "        pos = np.argmin(S, 1)\n",
    "        for i in range(k):\n",
    "            mu[i, :] = np.mean(X[pos == i, :], 0)\n",
    "        simi = np.sum(tempmu-mu)\n",
    "    return mu"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def errfun(X, mu):\n",
    "    row, col = X.shape\n",
    "    k = mu.shape[0]\n",
    "    err = 0\n",
    "    S = np.zeros((row, k))\n",
    "    for i in range(k):\n",
    "        S[:, i] = np.sum((X - mu[i, :]) ** 2, 1)\n",
    "    pos = np.argmin(S, 1)\n",
    "    for i in range(k):\n",
    "        err += np.sum((X[pos == i, :]-mu[i, :])**2)\n",
    "    return err/row"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 加载数据函数\n",
    "def loadData(filename):\n",
    "    data = pd.read_csv(filename, sep='\\s+', header=None)\n",
    "    data = data.as_matrix()\n",
    "    return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 导入数据\n",
    "X = loadData('hw4_kmeans_train.dat')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2.71678714378\n"
     ]
    }
   ],
   "source": [
    "# Q19\n",
    "err = 0\n",
    "for i in range(100):\n",
    "    mu = kMean(2, X)\n",
    "    err += errfun(X, mu)\n",
    "print(err/100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.79117604501\n"
     ]
    }
   ],
   "source": [
    "# Q20\n",
    "err = 0\n",
    "for i in range(100):\n",
    "    mu = kMean(10, X)\n",
    "    err += errfun(X, mu)\n",
    "print(err/100)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
